We prove that for $c>0$ a sufficiently small universal constant that a random set of $c d^2/\log^4(d)$ independent Gaussian random points in $\mathbb{R}^d$ lie on a common ellipsoid with high probability. This nearly establishes a conjecture of~\cite{SaundersonCPW12}, within logarithmic factors. The latter conjecture has attracted significant attention over the past decade, due to its connections to machine learning and sum-of-squares lower bounds for certain statistical problems.

The Forster transform is a method of regularizing a dataset by placing it in {\em radial isotropic position} while maintaining some of its essential properties. Forster transforms have played a key role in a diverse range of settings spanning computer science and functional analysis. Prior work had given {\em weakly} polynomial time algorithms for computing Forster transforms, when they exist. Our main result is the first {\em strongly polynomial time} algorithm to compute an approximate Forster transform of a given dataset or certify that no such transformation exists. By leveraging our strongly polynomial Forster algorithm, we obtain the first strongly polynomial time algorithm for {\em distribution-free} PAC learning of halfspaces. This learning result is surprising because {\em proper} PAC learning of halfspaces is {\em equivalent} to linear programming. Our learning approach extends to give a strongly polynomial halfspace learner in the presence of random classification noise and, more generally, Massart noise.

We study the fundamental task of outlier-robust mean estimation for heavy-tailed distributions in the presence of sparsity. Specifically, given a small number of corrupted samples from a high-dimensional heavy-tailed distribution whose mean $\mu$ is guaranteed to be sparse, the goal is to efficiently compute a hypothesis that accurately approximates $\mu$ with high probability. Prior work had obtained efficient algorithms for robust sparse mean estimation of light-tailed distributions. In this work, we give the first sample-efficient and polynomial-time robust sparse mean estimator for heavy-tailed distributions under mild moment assumptions. Our algorithm achieves the optimal asymptotic error using a number of samples scaling logarithmically with the ambient dimension. Importantly, the sample complexity of our method is optimal as a function of the failure probability $\tau$, having an additive $\log(1/\tau)$ dependence. Our algorithm leverages the stability-based approach from the algorithmic robust statistics literature, with crucial (and necessary) adaptations required in our setting. Our analysis may be of independent interest, involving the delicate design of a (non-spectral) decomposition for positive semi-definite matrices satisfying certain sparsity properties.

我们研究了Massart噪声存在下PAC学习半空间的复杂性。在这个问题中，我们得到了I.I.D.标记的示例$（\ mathbf {x}，y）\ in \ mathbb {r}^n \ times \ {\ pm 1 \} $，其中$ \ mathbf {x} $的分布是任意的，标签$ y y y y y y。 $是$ f（\ mathbf {x}）$的MassArt损坏，对于未知的半空间$ f：\ mathbb {r}^n \ to \ to \ {\ pm 1 \} $，带有翻转概率$ \ eta（\ eta）（\ eta） Mathbf {x}）\ leq \ eta <1/2 $。学习者的目的是计算一个小于0-1误差的假设。我们的主要结果是该学习问题的第一个计算硬度结果。具体而言，假设学习错误（LWE）问题（LWE）问题的（被认为是广泛的）超指定时间硬度，我们表明，即使最佳，也没有多项式时间MassArt Halfspace学习者可以更好地达到错误的错误，即使是最佳0-1错误很小，即$ \ mathrm {opt} = 2^{ - \ log^{c}（n）} $对于任何通用常数$ c \ in（0，1）$。先前的工作在统计查询模型中提供了定性上类似的硬度证据。我们的计算硬度结果基本上可以解决Massart Halfspaces的多项式PAC可学习性，这表明对该问题的已知有效学习算法几乎是最好的。

我们研究了测试有序域上的离散概率分布是否是指定数量的垃圾箱的直方图。$ k $的简洁近似值的最常见工具之一是$ k $ [n] $，是概率分布，在一组$ k $间隔上是分段常数的。直方图测试问题如下：从$ [n] $上的未知分布中给定样品$ \ mathbf {p} $，我们想区分$ \ mathbf {p} $的情况从任何$ k $ - 组织图中，总变化距离的$ \ varepsilon $ -far。我们的主要结果是针对此测试问题的样本接近最佳和计算有效的算法，以及几乎匹配的（在对数因素内）样品复杂性下限。具体而言，我们表明直方图测试问题具有样品复杂性$ \ widetilde \ theta（\ sqrt {nk} / \ varepsilon + k / \ varepsilon^2 + \ sqrt {n} / \ varepsilon^2）$。

我们研究了学习单个神经元的基本问题，即$ \ mathbf {x} \ mapsto \ sigma（\ mathbf {w} \ cdot \ cdot \ mathbf {x}）$单调激活$ \ sigma $ \ sigma： \ mathbb {r} \ mapsto \ mathbb {r} $，相对于$ l_2^2 $ -loss，在存在对抗标签噪声的情况下。具体来说，我们将在$（\ mathbf {x}，y）\ in \ mathbb {r}^d \ times \ times \ mathbb {r} $上给我们从$（\ mathbf {x}，y）\ on a发行$ d $中给我们标记的示例。 }^\ ast \ in \ mathbb {r}^d $ achieving $ f（\ mathbf {w}^\ ast）= \ epsilon $，其中$ f（\ mathbf {w}）= \ m马理bf {e} （\ mathbf {x}，y）\ sim d} [（\ sigma（\ mathbf {w} \ cdot \ mathbf {x}） - y）^2] $。学习者的目标是输出假设向量$ \ mathbf {w} $，以使$ f（\ m athbb {w}）= c \，\ epsilon $具有高概率，其中$ c> 1 $是通用常数。作为我们的主要贡献，我们为广泛的分布（包括对数 - 循环分布）和激活功能提供有效的恒定因素近似学习者。具体地说，对于各向同性对数凸出分布的类别，我们获得以下重要的推论：对于逻辑激活，我们获得了第一个多项式时间常数因子近似（即使在高斯分布下）。我们的算法具有样品复杂性$ \ widetilde {o}（d/\ epsilon）$，这在多毛体因子中很紧。对于relu激活，我们给出了一个有效的算法，带有样品复杂性$ \ tilde {o}（d \，\ polylog（1/\ epsilon））$。在我们工作之前，最著名的常数因子近似学习者具有样本复杂性$ \ tilde {\ omega}（d/\ epsilon）$。在这两个设置中，我们的算法很简单，在（正规）$ L_2^2 $ -LOSS上执行梯度散发。我们的算法的正确性取决于我们确定的新结构结果，表明（本质上是基本上）基础非凸损失的固定点大约是最佳的。

我们研究列表可解码的稀疏平均估计问题。具体来说，对于（0，1/2）$的参数$ \ alpha \，我们获得了$ \ mathbb {r}^n $，$ \ lfloor \ alpha m \ rfloor $的$ m $点。来自分销$ d $的样品，带有未知$ k $ -sparse的平均$ \ mu $。没有对剩余点的假设，该点构成了数据集的大多数。目标是返回包含矢量$ \ widehat \ mu $的候选人列表，以便$ \ | \ widehat \ mu - \ mu \ | _2 $很小。先前的工作研究了在密集设置中可列表可调式估计的问题。在这项工作中，我们开发了一种新颖的，概念上的简单技术，用于列表可解码的均值估计。作为我们方法的主要应用，我们为列表可解码的稀疏平均值估计提供了第一个样本和计算有效算法。特别是，对于带有``认证有限的''$ t $ t $ thements in $ k $ -sparse方向和足够轻的尾巴的发行版，我们的算法达到了$（1/\ alpha）^{o（1/t）的错误（1/\ alpha） } $带有示例复杂性$ m =（k \ log（n））^{o（t）}/\ alpha $和运行时间$ \ mathrm {poly}（mn^t）$。对于高斯嵌入式的特殊情况，我们的算法实现了$ \ theta（\ sqrt {\ log（1/\ alpha）}）$的最佳错误保证，并具有Quasi-PolyNomial样本和计算复杂性。我们通过几乎匹配的统计查询和低度多项式测试的下限来补充上限。

我们建立了最佳的统计查询（SQ）下限，以鲁棒地学习某些离散高维分布的家庭。特别是，我们表明，没有访问$ \ epsilon $ -Cruntupted二进制产品分布的有效SQ算法可以在$ \ ell_2 $ -error $ o（\ epsilon \ sqrt {\ log（\ log（1/\ epsilon））内学习其平均值}）$。同样，我们表明，没有访问$ \ epsilon $ - 腐败的铁磁高温岛模型的有效SQ算法可以学习到总变量距离$ O（\ Epsilon \ log（1/\ Epsilon））$。我们的SQ下限符合这些问题已知算法的错误保证，提供证据表明这些任务的当前上限是最好的。在技​​术层面上，我们为离散的高维分布开发了一个通用的SQ下限，从低维矩匹配构建体开始，我们认为这将找到其他应用程序。此外，我们介绍了新的想法，以分析这些矩匹配的结构，以进行离散的单变量分布。

我们研究了在存在$ \ epsilon $ - 对抗异常值的高维稀疏平均值估计的问题。先前的工作为此任务获得了该任务的样本和计算有效算法，用于辅助性Subgaussian分布。在这项工作中，我们开发了第一个有效的算法，用于强大的稀疏平均值估计，而没有对协方差的先验知识。对于$ \ Mathbb r^d $上的分布，带有“认证有限”的$ t $ tum-矩和足够轻的尾巴，我们的算法达到了$ o（\ epsilon^{1-1/t}）$带有样品复杂性$的错误（\ epsilon^{1-1/t}） m =（k \ log（d））^{o（t）}/\ epsilon^{2-2/t} $。对于高斯分布的特殊情况，我们的算法达到了$ \ tilde o（\ epsilon）$的接近最佳错误，带有样品复杂性$ m = o（k^4 \ mathrm {polylog}（d）（d））/\ epsilon^^ 2 $。我们的算法遵循基于方形的总和，对算法方法的证明。我们通过统计查询和低度多项式测试的下限来补充上限，提供了证据，表明我们算法实现的样本时间 - 错误权衡在质量上是最好的。

非高斯分量分析（NGCA）是以下分布学习问题：给予I.I.D.来自$ \ mathbb {r} ^ d $的分布上的样本，这是一个隐藏方向的非高斯和一个独立的标准高斯在正交方向上，目标是近似隐藏方向$ v $。先前的工作\ Cite {DKS17-SQ}提供了在单变量非高斯分配$ a $的适当时刻匹配条件下为NGCA提供信息计算权衡的正式证据。当分配$ a $是离散的时，后者的结果不适用。自然问题是信息计算权衡是否持续存在。在本文中，我们通过在规定的技术意义上获得$ a $的规范中的NGCA的样本和计算有效的算法来回答阴性的问题。在算法中利用的关键工具是LATTICE基础减少的LLL方法\ Cite {LLL82}。